#include "../tools.h"


class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        vector<pair<int, int>> arr;
        int size = profits.size();
        for(int i = 0; i < size; ++i){
            arr.emplace_back(capital[i], profits[i]);
        }
        sort(arr.begin(), arr.end());

        int cur = 0;
        priority_queue<int, vector<int>, less<int>> qMax;
        while(k--){
            for(; cur < size; ++cur){
                if(arr[cur].first <= w) qMax.push(arr[cur].second);
                else break;
            }
            if(!qMax.empty()){
                w += qMax.top();
                qMax.pop();
            }
        }
        return w;
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    // int k = 2, w = 0;
    // vector<int> profits = {1,2,3};
    // vector<int> capital = {0,1,1};

    int k = 3, w = 0;
    vector<int> profits = {1,2,3};
    vector<int> capital = {0,1,2};

    cout << sol.findMaximizedCapital(k, w, profits, capital) << endl;

    return 0;
}
